package com.leetcode.根据数据结构分类.队列;

import java.util.Stack;

/**
 * @author: ZhouBert
 * @date: 2020/11/21
 * @description: https://leetcode-cn.com/problems/implement-queue-using-stacks/
 * 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作（push、pop、peek、empty）：
 */
public class A_232_用栈实现队列 {


	/**
	 * target adt
	 * 通过模拟，可以使用两个栈实现。
	 * 当需要 deQueue 时，将 outStack 弹出即可；如果 outStack is Empty -> 将 inStack 的数据放入 outStack
	 */
	static class MyQueue {

		Stack<Integer> inStack;
		Stack<Integer> outStack;
		/**
		 * 记录总实际容量
		 */
		int size;

		/**
		 * Initialize your data structure here.
		 */
		public MyQueue() {
			inStack = new Stack<>();
			outStack = new Stack<>();
			size = 0;
		}

		/**
		 * Push element x to the back of queue.
		 * enQueue
		 */
		public void push(int x) {
			inStack.push(x);
			size++;
		}

		/**
		 * Removes the element from in front of queue and returns that element.
		 * 既然假设所有操作有效，那就不用处理异常了
		 */
		public int pop() {
			adjustOutStack();
			size--;
			//从 outStack 出栈
			return outStack.pop();
		}

		/**
		 * Get the front element.
		 */
		public int peek() {
			adjustOutStack();
			return outStack.peek();
		}

		/**
		 * Returns whether the queue is empty.
		 */
		public boolean empty() {
			return size == 0;
		}

		/**
		 * 将 inStack 的元素放入 outStack
		 */
		private void adjustOutStack(){
			if (outStack.isEmpty()) {
				while (!inStack.isEmpty()) {
					outStack.push(inStack.pop());
				}
			}
		}

	}
}
